#ifndef _SLINKLIST_H_
#define _SLINKLIST_H_

#include "SNode.hpp"
#include <iostream>

/**
 * @brief 
 *  单链表的实现:这个是带有头结点的链表
 * @tparam ElemType 
 */
template <typename ElemType>
class SLinkList
{
private:
    /* data */
public:
    SLinkList(/* args */);
    SLinkList(const ElemType *elems, int n);
    ~SLinkList();
    SLinkList(const SLinkList &other); // 深拷贝
    SLinkList &operator=(const SLinkList &e);
    void Clear();
    void Traverse(void (*visit)(const ElemType &e)) const; // 遍历
    int GetLength() const;
    int InsertElem(const ElemType &e);
    int InsertElem(int i, const ElemType &e);
    int DeleteElem(int i, ElemType &e);      // 返回状态
    int LocateElem(const ElemType &e) const; // 返回元素所在的位置
    int GetElem(int i, ElemType &e) const;   //返回状态,取得的元素放在e内
    int SetElem(int i, const ElemType &e);

protected:
    SNode<ElemType> *head;
    int length;
};

template <typename ElemType>
SLinkList<ElemType>::SLinkList(/* args */)
{
    head = new SNode<ElemType>;
    length = 0;
}

template <typename ElemType>
SLinkList<ElemType>::SLinkList(const ElemType *elems, int n)
{
    head = new SNode<ElemType>;
    SNode<ElemType> *p = head;
    for (int i = 0; i < n; i++)
    {
        p->next = new SNode<ElemType>(elems[i]);
        p = p->next;
    }
    length = n;
}

template <typename ElemType>
void SLinkList<ElemType>::Clear()
{
    length = 0;
    SNode<ElemType> *p = head->next;
    while (p)
    {
        head->next = p->next;
        delete p;
        p = head->next;
    }
}

template <typename ElemType>
SLinkList<ElemType>::~SLinkList()
{
    Clear();
    delete head;
}

template <typename ElemType>
SLinkList<ElemType>::SLinkList(const SLinkList &other)
{
    length = other.length;
    head = new SNode<ElemType>;
    SNode<ElemType> *q = other.head->next, *p = head;
    while (q)
    {
        p->next = new SNode<ElemType>(q->data);
        q = q->next;
        p = p->next;
    }
}

template <typename ElemType>
SLinkList<ElemType> &SLinkList<ElemType>::operator=(const SLinkList<ElemType> &other)
{
    Clear();
    length = other.length;
    SNode<ElemType> *q = other.head->next, *p = head;
    while (q)
    {
        p->next = new SNode<ElemType>(q->data);
        q = q->next;
        p = p->next;
    }
    return *this;
}

template <typename ElemType>
void SLinkList<ElemType>::Traverse(void (*visit)(const ElemType &e)) const
{
    SNode<ElemType> *p = head->next;
    while (p)
    {
        (*visit)(p->data);
        p = p->next;
    }
}

template <typename ElemType>
int SLinkList<ElemType>::GetLength() const
{
    return length;
}

template <typename ElemType>
int SLinkList<ElemType>::InsertElem(const ElemType &e)
{
    SNode<ElemType> *p = head;
    while (p->next)
    {
        p = p->next;
    }
    p->next = new SNode<ElemType>(e);
    length++;
    return 1;
}

template <typename ElemType>
int SLinkList<ElemType>::InsertElem(int i, const ElemType &e)
{
    if (i < 1 || i > length)
        return 0;
    else
    {
        SNode<ElemType> *p = head, *q;
        for (int count = 1; count < i; count++)
        {
            p = p->next;
        }
        q = new SNode<ElemType>(e, p->next);
        p->next = q;
        length++;
        return 1;
    }
}

template <typename ElemType>
int SLinkList<ElemType>::DeleteElem(int i, ElemType &e)
{
    if (i < 1 || i > length)
        return 0;
    else
    {
        SNode<ElemType> *p = head, *q;
        for (int count = 1; count < i; count++)
        {
            p = p->next;
        }
        q = p->next;
        e = q->data;
        p->next = q->next;
        delete q;
        length--;
        return 1;
    }
}

template <typename ElemType>
int SLinkList<ElemType>::LocateElem(const ElemType &e) const
{
    SNode<ElemType> *p = head->next;
    int i = 1;
    while (p)
    {
        if (p->data == e)
            return i;
        else
        {
            p = p->next;
            i++;
        }
    }
    return 0;
}

template <typename ElemType>
int SLinkList<ElemType>::GetElem(int i, ElemType &e) const
{
    if (i < 1 || i > length)
        return 0;
    else
    {
        SNode<ElemType> *p = head->next;
        for (int count = 1; count < i; count++)
        {
            p = p->next;
        }
        e = p->data;
        return 1;
    }
}

template <typename ElemType>
int SLinkList<ElemType>::SetElem(int i, const ElemType &e)
{
    if (i < 1 || i > length)
        return 0;
    else
    {
        SNode<ElemType> *p = head->next;
        for (int count = 1; count < i; count++)
        {
            p = p->next;
        }
        p->data = e;
        return 1;
    }
}

#endif // !_SLINKLIST_H_
